#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

int findLeftBottom(BinaryTreeNode* root) {
  int left_bottom = root->value;
  deque<BinaryTreeNode*> node_deque1;
  deque<BinaryTreeNode*> node_deque2;
  node_deque1.push_back(root);
  while (!node_deque1.empty()) {
    auto front_node = node_deque1.front();
    if (front_node->left) {
      node_deque2.push_back(front_node->left);
    }
    if (front_node->right) {
      node_deque2.push_back(front_node->right);
    }
    node_deque1.pop_front();
    if (node_deque1.empty()) {
      if (!node_deque2.empty())
        left_bottom = node_deque2.front()->value;
      swap(node_deque1, node_deque2);
    }
  }
  return left_bottom;
}

int main() {
  vector<int> vec = {8, 6, 10, 5, 7, 9, 11};
  BinaryTreeNode* root = CreateBinaryTree(vec);
  int ret = findLeftBottom(root);
  cout << ret << endl;

  return 0;
}
